package day2_linkedlist.leetcode;

/**
 * 排序链表
 * @author yuisama
 * @date 2021/12/25 13:51
 **/
public class Num148 {
    /**
     * 传入链表头结点，返回排序后链表头结点
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode middle = middle(head);
        ListNode x = head;
        while (x.next != middle) {
            x = x.next;
        }
        // 此时x在middle的前驱
        x.next = null;
        // 将左半区间排序
        ListNode l1 = sortList(head);
        // 排序右半区间
        ListNode l2 = sortList(middle);
        // 合并l1 与 l2
        return merge(l1,l2);
    }

    /**
     * 合并两个升序子链表为一个大的升序链表(迭代写法)
     * @param l1
     * @param l2
     * @return
     */
    private ListNode merge(ListNode l1, ListNode l2) {
        ListNode dummyHead = new ListNode(-1);
        ListNode tail = dummyHead;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                tail.next = l1;
                tail = l1;
                l1 = l1.next;
            }else {
                tail.next = l2;
                tail = l2;
                l2 = l2.next;
            }
        }
        if (l1 != null) {
            tail.next = l1;
        }
        if (l2 != null) {
            tail.next = l2;
        }
        return dummyHead.next;
    }
//    private ListNode merge(ListNode l1, ListNode l2) {
//        if (l1 == null) {
//            return l2;
//        }
//        if (l2 == null) {
//            return l1;
//        }
//        if (l1.val <= l2.val) {
//            l1.next = merge(l1.next,l2);
//            return l1;
//        }else {
//            l2.next = merge(l1,l2.next);
//            return l2;
//        }
//    }

    /**
     * 找到链表中间结点
     * @param head
     * @return
     */
    private ListNode middle(ListNode head) {
        ListNode fir = head,sec = head;
        while (fir != null && fir.next != null) {
            fir = fir.next.next;
            sec = sec.next;
        }
        return sec;
    }
}